/**
 * 快速排序
 * @param {*} arr
 * @param {*} start
 * @param {*} end
 */
function quickSort(arr, start, end) {
  if (end - start <= 1) return
  let i = start
  let j = end
  let key = arr[i]
  let left = false
  let right = true
  while (i < j) {
    if (right)
      if (arr[j] < key) {
        arr[i] = arr[j]
        right = false
        left = true
      } else {
        j--
      }
    if (left)
      if (arr[i] > key) {
        left = false
        right = true
        arr[j] = arr[i]
      } else {
        i++
      }
  }
  arr[i] = key
  quickSort(arr, start + 1, i)
  quickSort(arr, i + 1, end)
  return arr
}
console.log(quickSort([1, 2, 5, 7, 8, 0, 9], 0, 6))
